The present invention relates generally to computer networks and, more specifically, to a shared spanning tree protocol for defining a plurality of loop-free paths within a computer network.
Many organizations, including businesses, governments and educational institutions, utilize computer networks so that employees and others may share and exchange information and/or resources. A computer network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that xe2x80x9csourcesxe2x80x9d (i.e., transmits) or xe2x80x9csinksxe2x80x9d (i.e., receives) data frames over the communications media. A common type of computer network is a local area network (xe2x80x9cLANxe2x80x9d) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (xe2x80x9cWANxe2x80x9d) or internet that may span an entire country or continent.
One or more intermediate devices is often used to couple LANs together and allow the corresponding entities to exchange information. For example, a switch may be utilized to provide a xe2x80x9cswitchingxe2x80x9d function for transferring information, such as data frames, among entities of a computer network. Typically, the switch is a computer and includes a plurality of ports that couple the switch to the other entities. The switching function includes receiving data at a source port from an entity and transferring that data to at least one destination port for receipt by another entity.
In addition, most computer networks include redundant communications paths so that a failure of any given link does not isolate any portion of the network. Such networks are typically referred to as meshed or partially meshed networks. The existence of redundant links, however, may cause the formation of circuitous paths or xe2x80x9cloopsxe2x80x9d within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely.
Furthermore, some devices, such as bridges or switches, replicate frames whose destination is not known resulting in a proliferation of data frames along loops. The resulting traffic effectively overwhelms the network. Other intermediate devices, such as routers, that operate at higher hierarchical layers, such as the Internetwork Layer of the Transmission Control Protocol/Internet Protocol (xe2x80x9cTCP/IPxe2x80x9d) reference model within the protocol stack, deliver data frames and learn the addresses of entities on the network differently than most bridges or switches, such that routers are generally not susceptible to sustained looping problems.
To avoid the formation of loops, intermediate devices, such as bridges or switches, execute what is known as a spanning tree algorithm. This algorithm effectively xe2x80x9cseversxe2x80x9d the redundant links within network segments. More specifically, switches exchange special messages called bridge protocol data unit (BPDU) frames that allow them to calculate a spanning tree, which is a subset of the network segment that is loop-free (i.e., a tree) and yet connects every pair of LANs within the segment (i.e., the tree is spanning). The BPDU frames contain sufficient information, such as the relative cost of transmitting data frames over the links and interconnecting LANs, for the switches to discover a loop-free tree. Using this information, the switches calculate the tree in accordance with the algorithm and typically elect to sever or block all but one of the redundant links or communications paths. The spanning tree algorithm and the BPDU messages are well-known and documented (see IEEE Standard 802.1D).
In particular, execution of the spanning tree algorithm typically causes the switches to elect a single switch, among all the switches within each network segment, to be the xe2x80x9crootxe2x80x9d switch. The root is the switch having the lowest identifier (switch ID) of all switches in the particular network segment. Switch IDs, moreover, typically include a fixed portion and a settable portion. Accordingly, by modifying the settable portion of the ID of a given switch, a network administrator may xe2x80x9cforcexe2x80x9d the network to elect that switch as the root. In addition, for each LAN coupled to more than one switch, a xe2x80x9cdesignated switchxe2x80x9d is elected which will forward frames from the LAN toward the root. The designated switch is typically the closest switch to the root.
Each switch also chooses a port (e.g., the xe2x80x9croot portxe2x80x9d) which gives the best path from the switch to the root and selects those ports that are to be included in the spanning tree (i.e., the root port and any port for which the switch has been elected as a designated switch). These ports are placed in a forwarding mode so that data frames may be forwarded to and from the ports and thus onto the corresponding paths or links. Ports not included within the spanning are placed in a blocking mode. When a port is in the blocking mode, the associated switch will not forward any data frames to or from that port.
As links fail or are repaired or as new links are added to a network, the spanning tree is re-calculated. In response, ports may transition from the blocking mode to the forwarding mode and vice versa. Rather than transition directly from the blocking mode to the forwarding mode, ports transition through two intermediate states: a listening state and a learning state. In the listening state, a port waits for information suggesting that it should return to the blocked mode. If, at the expiration of a timer, no such information has been received, the port transitions to the learning state. In the learning state, a port still blocks the forwarding of frames but received frames are examined and the location information contained therein, including the source of the frame, is stored. At the expiration of a second timer, the port finally transitions to the forwarding mode where frames may be forwarded from and received at the port.
A computer network may also be segregated into a series of network groups. For example, U.S. Pat. No. 5,394,402, issued on Feb. 28, 1995 to Floyd E. Ross (the xe2x80x9c""402 Patentxe2x80x9d) discloses an arrangement that is capable of associating any port of a switch with any particular segregated network group. Specifically, according to the ""402 Patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, Ross discloses a switch or hub for a segmented virtual local area network with shared media access that associates VLAN designations with at least one internal port and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each internal port is stored in a memory portion of the switch such that every time a message is received by the switch on an internal port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in a memory based on the internal port where the message originated. In addition to the ""402 patent, an IEEE standards committee is preparing a standard for Virtual Bridged Local Area Networks. See IEEE Standard 802.1Q (draft).
In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. Ross, in fact, states that an objective of his VLAN arrangement is to allow all ports and entities of the network having the same VLAN designation to interchange messages by associating a VLAN designation with each message. Thus, those entities having the same VLAN designation function as if they are all part of the same LAN. Message exchanges between parts of the network having different VLAN designations are specifically prevented in order to preserve the boundaries of each VLAN segment.
Having defined a segregated computer network, several xe2x80x9csolutionsxe2x80x9d have been proposed for overlaying spanning trees on these virtually segregated network groups. The IEEE 802.1Q standards committee, for example, has proposed defining a single spanning tree for all VLAN designations in the computer network. That is, the switches exchange conventional BPDUs in the accustomed manner so as to define a single forwarding topology irrespective of the various VLAN designations that have been defined for the network. Thus, either all frames may be forwarded and received through a given port or no frames may be forwarded or received through the port. Since bridges and switches are typically pre-configured to exchange and process conventional BPDUs, this is a simple solution to implement.
Nonetheless, the IEEE solution has several drawbacks. For example, by defining a single spanning tree for a network having numerous VLAN designations, the IEEE solution does not allow for load balancing. That is, all data communication within the network follows the single forwarding topology defined by the one spanning tree. This may significantly degrade performance over certain, heavily utilized, portions of the network, severely limiting message throughput.
An alternative to the 802.1Q approach defines a separate spanning tree for each VLAN designation within the network and is currently being offered by Cisco Systems, Inc. See Cisco IOS VLAN Services document. With this approach, switches exchange BPDUs, each of which is tagged with a VLAN designation. That is, tagged BPDUs are formulated and exchanged for each VLAN designation within the network. These tagged BPDUs are then processed by the switches so as to define a separate forwarding topology or spanning tree for each VLAN designation. Thus, for a given port, messages associated with one VLAN designation may be forwarded and received whereas messages associated with a second VLAN designation may not.
By defining a separate forwarding topology for each VLAN designation which spans all entities associated with that designation, this solution supports load balancing throughout the network. It also avoids possible lost connectivity problems with portions of the network that may occur with the IEEE solution. There are, nonetheless, other drawbacks. First, this approach may not scale well to large networks. That is, as the number of VLAN designations increases, the number of tagged BPDUs being exchanged correspondingly increases. Accordingly, more communications bandwidth is consumed with BPDU traffic. Each BPDU, moreover, must be processed by the switches so as to calculate the corresponding spanning trees. Depending on the number of VLAN designations within the network, this may severely tax the processing and memory resources of the switches, degrading network efficiency.
It is an object of the present invention to provide a method and apparatus for defining a series of spanning trees that is scaleable to large networks having numerous virtual local area network designations.
It is a further object of the present invention to provide a method and apparatus for defining sufficient spanning trees to permit load balancing within the network.
It is a further object of the present invention to provide a protocol for defining a series of spanning trees without imposing a high processing load on the intermediate devices, thereby improving scalability.
It is a further object of the present invention to provide a protocol that is compatible with non-enabled devices (i.e., devices that do not execute the protocol) such as standard IEEE 802.1Q devices and the current devices from Cisco Systems, Inc.
Briefly, the invention comprises a shared spanning tree protocol (SSTP) for creating a plurality of spanning trees (i.e., loop-free paths) which are shared among one or more virtual local area network (VLAN) designations within a computer network. In one aspect of the invention, the SSTP manifests as an exchange of novel shared spanning tree protocol data units (SST-PDUs) among network devices so as to associate each VLAN designation with a single shared spanning tree. Each shared spanning tree, moreover, includes and is defined by a primary VLAN and may include any number of secondary VLANs.
The association of VLAN designations to shared spanning trees preferably depends on which forwarding topology is desired and on the anticipated load characteristics of the various VLANs and may be pre-configured along with the identities of the primary VLANs at one or more network devices. For example, one shared spanning tree may include a single high traffic VLAN (e.g., the primary VLAN) and several low traffic VLANs (e.g., the secondary VLANs) while a second shared spanning tree may include several moderate traffic VLANs. The total number of shared spanning trees implemented by SSTP is thus greater than one but less than the total number of VLANs. Data frames tagged with a particular VLAN designation are then distributed by the devices only along the shared spanning tree to which that VLAN has been associated by SSTP.
The contours (i.e., paths) of each shared spanning tree are defined through the exchange and processing of tagged bridge protocol data units (BPDUs). In another aspect of the invention, a device, pursuant to SSTP, formulates and exchanges BPDUs tagged only with primary VLAN designations. Devices generally do not exchange untagged BPDUs or BPDUs tagged with secondary VLAN designations, except to possibly satisfy backwards compatibility with non-SST enabled devices, including devices compatible with the IEEE 802.1Q standard. This substantially reduces the amount of communications traffic and processor load as compared to the per-VLAN spanning tree solution. By processing these primary VLAN tagged BPDUs, devices define the contours of each shared spanning tree. Through the exchange of SST-PDUs, devices then associate each VLAN designation with a single predefined shared spanning tree for subsequent data exchange.
Each SST-PDU frame preferably contains, among other information, a field corresponding to the VLAN tag appended to the frame and, if the tag corresponds to a primary VLAN, a list of the associated secondary VLANs. Another field may be used to set the time interval by which the receiving device is to keep the information contained in the SST-PDU. As VLANs are moved among shared spanning trees and new primary VLANs are designated, new SST-PDUs are generated and exchanged among network devices so as to replace the previously stored information.
In the illustrated embodiment, the SST protocol is implemented by means of a novel state machine engine executing at each device for each VLAN designation. Preferably, the state machine engine includes three states (i.e., disassociated, wait and associated) that transition in response to the information contained in SST-PDUs received by the device. In particular, the state machine engine copies information from each received SST-PDU into an association table organized by VLAN designation. If the information in the association table indicates that a given VLAN designation is associated with either none or more than one shared spanning tree, then the state machine engine enters the disassociated state and no data frames tagged with this VLAN designation are forwarded by the device.
As additional SST-PDUs are received, the device replaces stale information in its association table with newly received information. Once the association table indicates that the VLAN is associated with only one shared spanning tree, the state machine engine preferably enters a wait state while that condition is allowed to propagate throughout the network. After sufficient time has elapsed so as to ensure that the information has been received at each device and assuming no contrary information has been received, the state machine engine transitions to an associated state. Here, the VLAN is associated with exactly one shared spanning tree and data frames tagged with this VLAN designation may be received and forwarded by the device along this spanning tree.